package fibonacci;

/**
 * 一、斐波那契数列模型
 * 1. 求第 n 个泰波那契数
 * 2024-10-18
 */
public class demo1 {
    public int tribonacci(int n) {
        //1. 创建 dp 表
        int[] dp = new int[n+1];

        //处理边界情况，避免 n 太小，导致后面越界
        if(n == 0)
            return 0;
        if(n == 1 || n == 2)
            return 1;

        //2. 初始化
        dp[0] = 0;  dp[1] = dp[2] = 1;

        //3. 填表
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        }

        //4. 返回值
        return dp[n];
    }


    /**
     * 空间优化
     * 滚动数组
     */
    public int roll(int n) {

        if(n == 0)  return 0;
        if(n == 1 || n == 2)  return 1;

        int a = 0, b = 1, c = 1, d = 0;
        for (int i = 3; i <= n; i++) {
            d = a + b + c;
            a = b;
            b = c;
            c = d;
        }
        return d;
    }
}
